package LeetCode.LC103;

import java.util.*;

/**
 * @author corn
 * @create 2020-08-07-20:12
 */

/**
 * 103. 二叉树的锯齿形层次遍历
 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。
 * （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Stack[] s = new Stack[2];
        s[0] = new Stack<TreeNode>();
        s[1] = new Stack<TreeNode>();
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        List<Integer> tmp = new ArrayList<Integer>();
        if(root == null) {
            return ret;
        }
        int now = 0;
        s[now].push(root);
        while(!s[0].empty() || !s[1].empty()) {
            TreeNode t = (TreeNode)s[now].pop();
            tmp.add(t.val);
            if(now == 0) {
                if(t.left != null)
                    s[1 - now].push(t.left);
                if(t.right != null)
                    s[1 - now].push(t.right);
            }
            else {
                if(t.right != null)
                    s[1 - now].push(t.right);
                if(t.left != null)
                    s[1 - now].push(t.left);
            }
            if(s[now].empty()) {
                now = 1 - now;
                ret.add(new ArrayList<Integer>(tmp));
                tmp.clear();
            }
        }
        return ret;
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

}
